package com.xsherl.leetcode.solution;

public class TrappingRainWater {

    /**
     * 1. 找出最高的柱子
     * 2. 从左到右计算雨的数量，一直计算到最高的柱子为止
     *    计算方式为：1. 如果当前柱子的高度h小于目前左边最高的柱子高度leftMax,则这个柱子一定存了雨水，这个柱子上雨的数量等于leftMax - h;
     *              2. 如果h >= leftMax,说明这个柱子就是左边池子的新的左边高度，更新leftMax的值
     * 3. 同样从右到左计算计算雨的数量，一直计算到最高的柱子为止
     *
     * @param height n == height.length
     *               0 <= n <= 3 * 10^4
     *               0 <= height[i] <= 105
     */
    public int trap(int[] height) {
        int len = height.length;
        if (len == 0){
            return 0;
        }
        int trap = 0;
        int maxIndex = 0, max = 0;
        for (int i = 0; i < len; ++i){
            if (max < height[i]){
                max = height[i];
                maxIndex = i;
            }
        }
        int leftMax = 0;
        for (int i = 0; i <= maxIndex; ++i){
            int h = height[i];
            if (h < leftMax){
                trap += leftMax - h;
            } else {
                leftMax = h;
            }
        }
        int rightMax = 0;
        for (int i = len - 1; i >= maxIndex; --i){
            int h = height[i];
            if (h < rightMax){
                trap += rightMax - h;
            } else {
                rightMax = h;
            }
        }

        return trap;
    }

    public static void main(String[] args) {
        int[] height = {4,2,0,3,2,5};
        int trap = new TrappingRainWater().trap(height);
        System.out.println(trap);
    }

}
